package com.maptasksolver.struct.heap;

import com.maptasksolver.exceptions.*;

public class Heap {
	
	private int count = 0;
	private int maxCount = 0;
	
	private Treeable[] heap;
	
	public Heap(int maxCount) throws WrongParameter {
		if (maxCount < 1) throw new WrongParameter();
		
		this.maxCount = maxCount;
		heap = new Treeable[maxCount + 1];
	}
	
	public void add(Treeable node) throws WrongParameter, NodesCountLimitExceeded {
		if (node == null) throw new WrongParameter();
		if (count == maxCount) throw new NodesCountLimitExceeded();
		
		++count;
		heap[count] = node.clone();
		pushUp(count);		
	}
	
	public Treeable pop() throws EmptyTreeException {
		if (isEmpty()) throw new EmptyTreeException();
		Treeable res = heap[1].clone();
		swapNodes(1, count);
		heap[count] = null;
		--count;
		pushDown(1);		
		return res;		
	}
	
	public int getMaxCount() {
		return maxCount;
	}
	
	public int getCount() {
		return count;
	}
	
	public double getMin() {
		return heap[1].getValue();
	}
	
	public boolean isEmpty() {
		return count == 0;
	}
	
	private void pushUp(int pos) {
		while (pos > 1) {
			if (heap[pos].getValue() < heap[pos / 2].getValue()) {
				swapNodes(pos, pos / 2);
				pos /= 2;
			} else
				break;
		}
	}
	
	private void pushDown(int pos) {
		
		boolean l = hasLeftSon(pos), r = hasRightSon(pos);
		
		while (l || r) {		
			if (l && r) {
				int newPos = heap[pos * 2].getValue() < heap[pos * 2 + 1].getValue() ? 
						pos * 2 : pos * 2 + 1;
				if (heap[pos].getValue() > heap[newPos].getValue())
					swapNodes(pos, newPos);
				else 
					break;
				pos = newPos;
			}
			else if (l) {
				if (heap[pos].getValue() > heap[pos * 2].getValue())
					swapNodes(pos, pos * 2);
				else
					break;
				pos *= 2;
			} else if (r) {
				if (heap[pos].getValue() > heap[pos * 2 + 1].getValue())
					swapNodes(pos, pos * 2 + 1);
				else
					break;
				pos = pos * 2 + 1;
			}
			l = hasLeftSon(pos); r = hasRightSon(pos);				
		}		
	}
	
	private void swapNodes(int i, int j) {
		Treeable temp = heap[i];
		heap[i] = heap[j];
		heap[j] = temp;		
	}
	
	private boolean hasLeftSon(int pos) {
		return pos * 2 <= count;
	}
	
	private boolean hasRightSon(int pos) {
		return pos * 2 + 1 <= count;
	}

}
